//给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,5,11,5]
//输出：true
//解释：nums 可以分割成 [1, 5, 5] 和 [11] 。
//
// 示例 2：
//
//
//输入：nums = [1,2,3,5]
//输出：false
//解释：nums 不可以分为和相等的两部分
//
//
//
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 200
// 1 <= nums[i] <= 100
//
//
//
//
//
// 注意：本题与主站 416 题相同： https://leetcode-cn.com/problems/partition-equal-subset-
//sum/
//
// Related Topics 数学 字符串 模拟 👍 83 👎 0

//? 回溯 超时
function canPartition(nums: number[]): boolean {

    let sum = 0
    for (let i = 0; i < nums.length; i ++) {
        sum += nums[i]
    }
    if (sum % 2 === 1) return false
    let mid = sum / 2

    function backtracking(startIndex,count) {

        if (count > mid) return
        if (count === mid) {
            flag = true
            return;
        }
        for (let i = startIndex; i < nums.length; i ++) {
            count += nums[startIndex]
            backtracking(i + 1,count)
            count -= nums[startIndex]
        }
    }
    let flag = false
    backtracking(0,0)
    return flag

};
//? 动态规划-背包
function canPartition2(nums: number[]): boolean {

    const sum: number = nums.reduce((pre, cur) => pre + cur);
    if (sum % 2 === 1) return false;
    const bagSize: number = sum / 2;
    const goodsNum: number = nums.length;
    const dp: number[] = new Array(bagSize + 1).fill(0);
    for (let i = 0; i < goodsNum; i++) {
        // j >= nums[i]也保证数组不越界
        for (let j = bagSize; j >= nums[i]; j--) {
            // 这里以要寻找的数作为背包容量 因为本题中每一个元素的数值既是重量，也是价值。也因为遍历过程中的数不会超过此数
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    return dp[bagSize] === bagSize;
};
